CS255Spring 2018Lecture Notes
Design and Analysis of Algorithms
Videos of lectures are available.
Below are my lecture notes for the class so far.
They should serve as a rough guide to what was covered on any given day.
Frequently, however, I say more in class than is in these notes.
Also, I tend to dynamically correct typos on the board
that might appear in these lecture notes. So caveat emptor.
Week 1: [Jan 24 -- Probabilistic Analysis and Randomized Algorithms]
Week 2: [Jan 29 -- Analyzing the Hiring Problem, Generating Random Permutations] [Jan 31 -- Random Permutations, the Birthday Problem, Ball and Bins Arguments]
Week 3: [Feb 5 -- Streaks, Online Hiring Problem, Start Threads] [Feb 7 -- Multithreaded Algorithms]
Week 4: [Feb 12 -- More Multithreaded algorithms] [Feb 14 -- Race Conditions, Chess, Matrix Multiplication]
Week 5: [Feb 19 -- Spawn Sync Java, JOCL, PRAMs] [Feb 21 -- PRAM Sorting]
Week 6: [Feb 26 -- PRAMs and Maximal Independent Set] [Feb 28 -- Distributed Algorithms]
Week 7: [Mar 5 -- Byzantine Agreement - Map Reduce] [Mar 7 -- Map Reduce and PRAMs]
Week 8: [Mar 12 -- Practice Midterm] [Mar 14 -- Midterm]
Week 9: [Mar 19 -- Finish Map Reduce and PRAMs, Online Algorithms] [Mar 21 -- Finish Online Algorithms, Number Theoretic Algorithms]
Week 10: [Mar 26 - Spring Break] [Mar 28 - Spring Break]
Week 11: [Apr 2 -- Number Theoretic Algorithms, GCDs, Euclid's Algorithm, Groups] [Apr 4 -- Modular Arithmetic]
Week 12: [Apr 9 -- Chinese Remaindering, Discrete Log, RSA] [Apr 11 -- Primality Checking]
Week 13: [Apr 16 -- NP, NP-Completeness, Reductions] [Apr 18 -- NP-completeness of CIRCUIT-SAT, SAT, k-SAT]
Week 14: [Apr 23 -- Various NPC Problems] [Apr 25 -- TSP and SUBSET-SUM are NPC, Approximation Algorithms]
Week 15: [Apr 30 -- Approximation Algorithms] [May 2 -- Set Cover, Randomized Approximation Algorithms]
Week 16: [May 7 -- Weighted Vertex Cover - Fully p-time Approximation of Subset Sum] [May 9 -- The Probabilistic Method]
|